I got a brain teaser for you - it's not as simple as it sounds so please read and try to solve the issue. Before you ask if it's homework - it's not! I just wish to see if there's an elegant way of solving this. Here's the issue:

X-number of friends want's to go to the cinema and wish to be seated in the best available groups. Best case is that everyone sits together and worst case is that everyone sits alone. Fewer groups are preferred over more groups. Sitting alone is least preferred.

Input is the number of people going to the cinema and output should be an array of integer arrays that contains:

• Ordered combinations (most preferred are first)
• Number of people in each group

Below are some examples of number of people going to the cinema and a list of preferred combinations these people can be seated:

• 1 person: 1
• 2 persons: 2, 1+1
• 3 persons: 3, 2+1, 1+1+1
• 4 persons: 4, 2+2, 3+1, 2+1+1, 1+1+1+1
• 5 persons: 5, 3+2, 4+1, 2+2+1, 3+1+1, 2+1+1+1, 1+1+1+1+1
• 6 persons: 6, 3+3, 4+2, 2+2+2, 5+1, 3+2+1, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1

Example with more than 7 persons explodes in combinations but I think you get the point by now.

Question is: What does an algorithm look like that solves this problem? My language by choice is C# so if you could give an answer in C# it would be fantastic!